package dp;

public class D230817 {
    // 最长公共子串
    // 1. 枚举
    // 枚举两个字符串所有的起始位置
    // 然后从两个字符串的起始位置，向后检查字符是否相等
    // 维护一个长度最大的子串
    // 时间复杂度：O(n3)
    // 空间复杂度：O(n)
    public String LCS (String str1, String str2) {
        int length = 0;
        String res = "";
        //遍历s1每个起始点
        for(int i = 0; i < str1.length(); i++){
            //遍历s2每个起点
            for(int j = 0; j < str2.length(); j++){
                int temp = 0;
                StringBuilder temps = new StringBuilder();
                int x = i, y = j;
                //比较每个起点为始的子串
                while(x < str1.length() && y < str2.length() && str1.charAt(x) == str2.charAt(y)){
                    temps.append(str1.charAt(x));
                    x++;
                    y++;
                    temp++;
                }
                //更新更大的长度子串
                if(length < temp){
                    length = temp;
                    res = temps.toString();
                }
            }
        }
        return res;
    }

    // 2. 动态规划
    // 用一个二维数组记录 str1以第i个字符结尾 和 str2以第j个字符结尾时，最长公共子串的长度
    // 遍历两个字符串，如果字符相等，则 dp[i][j] = dp[i - 1][j - 1] + 1
    // 如果不相等，则 dp[i][j] = 0
    // 遍历的过程中更新最长公共子串，就是记录公共子串的位置 以及 长度
    // 时间复杂度：O(mn)
    // 空间复杂度：O(mn)
    public String LCS2 (String str1, String str2) {
        // 记录 str1以第i字符结尾 与 str2以第j个字符结尾时 的最长公共子串
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        // 记录公共子串尾部在 str1 中的下标 + 1
        int pos = 0;
        // 记录公共子串的程长度
        int max = 0;
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (max < dp[i][j]) {
                        // 更新最长公共子串
                        max = dp[i][j];
                        pos = i;
                    }
                } else {
                    // 不相等，已经不是公共子串了，置为 0
                    dp[i][j] = 0;
                }
            }
        }
        return str1.substring(pos - max, pos);
    }



    // 不同路径的数目(一)
    // 动态规划
    // 时间复杂度：O(mn)
    // 空间复杂度：O(mn)
    public int uniquePaths (int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    // 第一行 / 第一列，只有一种路径
                    dp[i][j] = 1;
                    continue;
                }
                // 路径数等于上方格子的路径数加上左方格子的路径数
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }


    // 数学组合
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    // 从左上角到右下角，总共需要往下走 m - 1 步，往右走 n - 1 步
    // 不同的走法路径在于 往下 和 往右 的组合情况
    // 在往下和往右的序列中，每种路径序列长度一样，序列一共有 m + n - 2 个位置
    // 选择其中 n - 1 个位置往下，即 C (n - 1) (m + n - 2)
    // 就是 (m + n - 2)! / ((n - 1)! X (m - 1)!)
    public int uniquePaths2 (int m, int n) {
        //防止溢出
        long res = 1;
        for(int i = 1; i < n; i++)
            //根据公式计算
            res = res * (m + i - 1) / i;
        return (int)res;
    }
}
